{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random,datetime,time,math\n",
    "from bisect import bisect_left\n",
    "from enum import Enum\n",
    "from math import exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _generate_parent(length, geneSet, get_fitness):\n",
    "    genes = []\n",
    "    while len(genes) < length:\n",
    "        sampleSize = min(length - len(genes), len(geneSet))\n",
    "        genes.extend(random.sample(geneSet, sampleSize))\n",
    "    fitness = get_fitness(genes)\n",
    "    return Chromosome(genes, fitness, Strategies.Create)\n",
    "\n",
    "def _mutate_custom(parent, custom_mutate, get_fitness):\n",
    "    childGenes = parent.Genes[:]\n",
    "    custom_mutate(childGenes)\n",
    "    fitness = get_fitness(childGenes)\n",
    "    return Chromosome(childGenes, fitness, Strategies.Mutate)\n",
    "\n",
    "\n",
    "def _crossover(parentGenes, index, parents, get_fitness, crossover, mutate,\n",
    "               generate_parent):\n",
    "    donorIndex = random.randrange(0, len(parents))\n",
    "    if donorIndex == index:\n",
    "        donorIndex = (donorIndex + 1) % len(parents)\n",
    "    childGenes = crossover(parentGenes, parents[donorIndex].Genes)\n",
    "    if childGenes is None:\n",
    "        # parent and donor are indistinguishable\n",
    "        parents[donorIndex] = generate_parent()\n",
    "        return mutate(parents[index])\n",
    "    fitness = get_fitness(childGenes)\n",
    "    return Chromosome(childGenes, fitness, Strategies.Crossover)\n",
    "\n",
    "\n",
    "def get_best(get_fitness, targetLen, optimalFitness, geneSet, display,\n",
    "             custom_mutate=None, custom_create=None, maxAge=None, poolSize=1,\n",
    "             crossover=None, maxSeconds=None):\n",
    "    if custom_mutate is None:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate(parent, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate_custom(parent, custom_mutate, get_fitness)\n",
    "\n",
    "    if custom_create is None:\n",
    "        def fnGenerateParent():\n",
    "            return _generate_parent(targetLen, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnGenerateParent():\n",
    "            genes = custom_create()\n",
    "            return Chromosome(genes, get_fitness(genes), Strategies.Create)\n",
    "\n",
    "    strategyLookup = {\n",
    "        Strategies.Create: lambda p, i, o: fnGenerateParent(),\n",
    "        Strategies.Mutate: lambda p, i, o: fnMutate(p),\n",
    "        Strategies.Crossover: lambda p, i, o:\n",
    "        _crossover(p.Genes, i, o, get_fitness, crossover, fnMutate,\n",
    "                   fnGenerateParent)\n",
    "    }\n",
    "\n",
    "    usedStrategies = [strategyLookup[Strategies.Mutate]]\n",
    "    if crossover is not None:\n",
    "        usedStrategies.append(strategyLookup[Strategies.Crossover])\n",
    "\n",
    "        def fnNewChild(parent, index, parents):\n",
    "            return random.choice(usedStrategies)(parent, index, parents)\n",
    "    else:\n",
    "        def fnNewChild(parent, index, parents):\n",
    "            return fnMutate(parent)\n",
    "\n",
    "    for timedOut, improvement in \\\n",
    "            _get_improvement(fnNewChild, fnGenerateParent, maxAge, poolSize,\n",
    "                             maxSeconds):\n",
    "        if timedOut:\n",
    "            return improvement\n",
    "        display(improvement)\n",
    "        f = strategyLookup[improvement.Strategy]\n",
    "        usedStrategies.append(f)\n",
    "        if not optimalFitness > improvement.Fitness:\n",
    "            return improvement\n",
    "\n",
    "\n",
    "def _get_improvement(new_child, generate_parent, maxAge, poolSize, maxSeconds):\n",
    "    startTime = time.time()\n",
    "    bestParent = generate_parent()\n",
    "    yield maxSeconds is not None and time.time() \\\n",
    "          - startTime > maxSeconds, bestParent\n",
    "    parents = [bestParent]\n",
    "    historicalFitnesses = [bestParent.Fitness]\n",
    "    for _ in range(poolSize - 1):\n",
    "        parent = generate_parent()\n",
    "        if maxSeconds is not None and time.time() - startTime > maxSeconds:\n",
    "            yield True, parent\n",
    "        if parent.Fitness > bestParent.Fitness:\n",
    "            yield False, parent\n",
    "            bestParent = parent\n",
    "            historicalFitnesses.append(parent.Fitness)\n",
    "        parents.append(parent)\n",
    "    lastParentIndex = poolSize - 1\n",
    "    pindex = 1\n",
    "    while True:\n",
    "        if maxSeconds is not None and time.time() - startTime > maxSeconds:\n",
    "            yield True, bestParent\n",
    "        pindex = pindex - 1 if pindex > 0 else lastParentIndex\n",
    "        parent = parents[pindex]\n",
    "        child = new_child(parent, pindex, parents)\n",
    "        if parent.Fitness > child.Fitness:\n",
    "            if maxAge is None:\n",
    "                continue\n",
    "            parent.Age += 1\n",
    "            if maxAge > parent.Age:\n",
    "                continue\n",
    "            index = bisect_left(historicalFitnesses, child.Fitness, 0,\n",
    "                                len(historicalFitnesses))\n",
    "            proportionSimilar = index / len(historicalFitnesses)\n",
    "            if random.random() < exp(-proportionSimilar):\n",
    "                parents[pindex] = child\n",
    "                continue\n",
    "            bestParent.Age = 0\n",
    "            parents[pindex] = bestParent\n",
    "            continue\n",
    "        if not child.Fitness > parent.Fitness:\n",
    "            child.Age = parent.Age + 1\n",
    "            parents[pindex] = child\n",
    "            continue\n",
    "        child.Age = 0\n",
    "        parents[pindex] = child\n",
    "        if child.Fitness > bestParent.Fitness:\n",
    "            bestParent = child\n",
    "            yield False, bestParent\n",
    "            historicalFitnesses.append(bestParent.Fitness)\n",
    "\n",
    "\n",
    "class Chromosome:\n",
    "    def __init__(self, genes, fitness, strategy):\n",
    "        self.Genes = genes\n",
    "        self.Fitness = fitness\n",
    "        self.Strategy = strategy\n",
    "        self.Age = 0\n",
    "\n",
    "\n",
    "class Strategies(Enum):\n",
    "    Create = 0,\n",
    "    Mutate = 1,\n",
    "    Crossover = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_fitness(genes, bitValues):\n",
    "    denominator = get_denominator(genes, bitValues)\n",
    "    if denominator == 0:\n",
    "        return 0\n",
    "\n",
    "    ratio = get_numerator(genes, bitValues) / denominator\n",
    "    return math.pi - math.fabs(math.pi - ratio)\n",
    "\n",
    "\n",
    "def display(candidate, startTime, bitValues):\n",
    "    timeDiff = datetime.datetime.now() - startTime\n",
    "    numerator = get_numerator(candidate.Genes, bitValues)\n",
    "    denominator = get_denominator(candidate.Genes, bitValues)\n",
    "    print(\"{}/{}\\t{}\\t{}\".format(\n",
    "        numerator,\n",
    "        denominator,\n",
    "        candidate.Fitness, timeDiff))\n",
    "\n",
    "\n",
    "def bits_to_int(bits, bitValues):\n",
    "    result = 0\n",
    "    for i, bit in enumerate(bits):\n",
    "        if bit == 0:\n",
    "            continue\n",
    "        result += bitValues[i]\n",
    "    return result\n",
    "\n",
    "\n",
    "def get_numerator(genes, bitValues):\n",
    "    return 1 + bits_to_int(genes[:len(bitValues)], bitValues)\n",
    "\n",
    "\n",
    "def get_denominator(genes, bitValues):\n",
    "    return bits_to_int(genes[len(bitValues):], bitValues)\n",
    "\n",
    "\n",
    "def mutate(genes, numBits):\n",
    "    numeratorIndex, denominatorIndex \\\n",
    "        = random.randrange(0, numBits), random.randrange(numBits,\n",
    "                                                         len(genes))\n",
    "    genes[numeratorIndex] = 1 - genes[numeratorIndex]\n",
    "    genes[denominatorIndex] = 1 - genes[denominatorIndex]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test(bitValues=[512, 256, 128, 64, 32, 16, 8, 4, 2, 1],\n",
    "             maxSeconds=None):\n",
    "        geneset = [i for i in range(2)]\n",
    "        startTime = datetime.datetime.now()\n",
    "\n",
    "        def fnDisplay(candidate):\n",
    "            display(candidate, startTime, bitValues)\n",
    "\n",
    "        def fnGetFitness(genes):\n",
    "            return get_fitness(genes, bitValues)\n",
    "\n",
    "        optimalFitness = 3.14159\n",
    "\n",
    "        def fnMutate(genes):\n",
    "            mutate(genes, len(bitValues))\n",
    "\n",
    "        length = 2 * len(bitValues)\n",
    "        best = get_best(fnGetFitness, length, optimalFitness,\n",
    "                                geneset, fnDisplay, fnMutate, maxAge=250,\n",
    "                                maxSeconds=maxSeconds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "679/405\t1.6765432098765432\t0:00:00\n",
      "687/401\t1.713216957605985\t0:00:00.000965\n",
      "703/403\t1.7444168734491314\t0:00:00.000965\n",
      "767/402\t1.907960199004975\t0:00:00.000965\n",
      "768/274\t2.802919708029197\t0:00:00.000965\n",
      "767/272\t2.8198529411764706\t0:00:00.000965\n",
      "1023/304\t2.9180537282322176\t0:00:00.000965\n",
      "991/305\t3.0340049793107338\t0:00:00.000965\n",
      "987/309\t3.089010549898033\t0:00:00.000965\n",
      "859/277\t3.101083032490975\t0:00:00.000965\n",
      "860/273\t3.133002156996436\t0:00:00.000965\n",
      "864/275\t3.1413671253614046\t0:00:00.001962\n",
      "1021/325\t3.1415384615384614\t0:00:00.009940\n",
      "355/113\t3.1415923868256037\t0:00:04.210775\n"
     ]
    }
   ],
   "source": [
    "test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
